This invention relates generally to the field of image processing and, more particularly, to the methods for implementing sliding-window digital image processing for associative operators such as MIN, MAX, AND, and OR.
In the arts, there are instances in digital image processing systems, either in hardware or software, where one would like to calculate some property of the image in a sliding rectangular window. For example, knowing the average value of pixels in a region around a central pixel gives an indication that is useful for certain noise removal algorithms. As such, knowing the minimum and maximum value of a pixel in a window can be used to identify image regions that are xe2x80x9cflatxe2x80x9d or considered background.
In order to calculate an average for an interval along a scan line, one can add up the pixel values in the interval. To calculate the sum of the pixel values in an interval that is displaced by one pixel, the value of the pixel leaving the interval can be subtracted and the pixel value of the one entering the interval can be added for a total of two operations required to calculate the sum of the new interval. For long intervals, this is much faster than recalculating the sum of all the pixels in the new interval. This works because the addition operation is associative, commutative, and has an inverse operation, namely subtraction. This technique can be expanded to incrementally calculate the sum of the pixels in a rectangle that is slightly displaced. All of these techniques have limitations to which the present invention is directed, namely, that in certain image processing algorithms one wants to calculate a minimum or maximum value of a sliding window of values and, since the min or max function does not have an inverse the above method is inapplicable. As such, if the length of the sliding window is n and the window is slid m times, then an obvious implementation will use on the order of m*(nxe2x88x921) operations.
What is needed in the art is a method which overcomes the limitations in the art and which is a faster implementation using less operations and whose time is better than proportional to the length of the window.
The present invention discloses a fast method of implementing sliding-window image processing for associative operators such as MIN, MAX, AND, and OR. For one dimension, the present method divides the image into blocks according to the sliding window size and for each block calculates two sets of partial results, one working from the left boundary of the block and the other working from the right boundary of the block. The partial results from two adjacent blocks can then be combined in one operation to give a final value for any window straddling two adjacent blocks. The total number of operations is proportional to 3M; where M is the scan length as compared to (nxe2x88x921)M using prior art; where n is the length of the sliding window. The present invention can be extended to two-dimensional arrays and can be extended to support arbitrary window sizes.
Often in a hardware or software digital imaging processing system a sliding window is employed across the digital image data and then, for each position of the window, a function of the windowed data is calculated. One example of a function which is often applied to such windowed data is operation of ADDITION. In this case, the value of the sum of a one-position displaced window is incrementally calculated from the sum of the original window by subtracting off the value that just left the sliding window and adding the value that just entered the sliding window. Because addition has an inverse operation, namely, SUBTRACTION, this methodology works well but it does not work at all for operations without an inverse such as MIN, MAX, AND, or OR. Even though these operations do not possess an inverse, the present invention utilizes the fact that these operations have an associative quality, i.e., (x op y) op z=x op (y op z). As such, the present invention provides an efficient method to speed up any operation that is without and inverse operation but is associative.
The present invention discloses a fast method of implementing sliding-window image processing for associative operators such as MIN, MAX, AND, and OR. For one dimension, the present method divides the image into blocks according to the sliding window size and for each block calculates two sets of partial results, one working from the left boundary of the block and the other working from the right boundary of the block. The partial results two adjacent blocks can then be combined in one operation to give a final value for any window straddling two adjacent blocks. Moreover, the present invention can not only be extended to arbitrary window sizes but can also be applied to each dimension independently.
Briefly, the method of the present invention involves the first step of, for a sliding window of size n, the data is first divided into (n+1)-element blocks. Then, for each element in the block starting from the left end of the block the operation is successively applied to the previous result and the next element of the block. Similarly, from the right end of the block the operation is successively applied to the previous result and the next element of the block. At this point, it should be understood that one does not need to calculate the operation across the entire block as this would be across n+1 elements and the sliding window contains only n elements. The next step of the method of the present invention involves the step of for each position of the sliding window determining which block or blocks lie under the sliding window and, if this is a single block, retrieving the value calculated for the elements of the sliding window, or if there are two blocks, combining the previously calculated values in each block corresponding to the part of the sliding window contained in the block. It takes nxe2x88x921 operations to calculate the left-end results in each block, nxe2x88x921 operations to calculate the right-end results in each block, and nxe2x88x921 operations to calculate the nxe2x88x921 possible overlap positions thereby generating a total of 3*nxe2x88x923 operations to calculate n+1 windowed results. Note that two of the sliding window positions do not overlap two blocks and no further calculation is necessary in these cases. This averages to less than 3 operations per calculated value.
For example, to calculate a MIN function in a sliding window of length n, an appropriate block size is n+1 because a window of size n always contains an edge of every block it intersects. Then, in each block, calculate and remember successive cumulative minimums from the left edge and then from the right edge. Now, for any position of the sliding window, the minimum in the sliding window can be calculated with at most one more MIN operation. If the sliding window is completely contained in a single block then either the left edge of the sliding window coincides with the left edge of the containing block or the right edge of the sliding window coincides with the right edge of the containing block and the minimum has already been calculated. If the sliding window overlaps two blocks then the minimum in the sliding window can be calculated by taking the minimum of the part of the left block overlapped by the sliding window and the part of the right block overlapped by the sliding window and both of these values have been previously calculated. The total number of operations for this example is (nxe2x88x921 operations per block for calculations from the left end of the block)+(nxe2x88x921 operations per block for calculations from the right end of the block)+(nxe2x88x921 operations to combine results for cases where the sliding window straddles two blocks)+(0 operations in the two cases when the sliding window is contained within a single block)=3nxe2x88x923 operations to handle n+1 positions of the sliding window or (3nxe2x88x923)M/(n+1) or about 3M, where M is the scan length, as compared to (nxe2x88x921)M using prior art; where n is the length of the sliding window.